package _18_剑指OfferII;

public class _009_剑指OfferII乘积小于K的子数组 {

    public static void main(String[] args) {

        _009_剑指OfferII乘积小于K的子数组 v = new _009_剑指OfferII乘积小于K的子数组();

        int[] ins = {10, 5, 2, 6};
        System.out.println(v.numSubarrayProductLessThanK(ins, 100));

    }

    // 二分查找， 计算小于k的连续子序列乘积
    // 首先，如果计算数组中每个序列的前缀积，首先需要想到的是，数据溢出问题
    // 无论如何都会数据溢出，如果替换成指数相加，就不会出现此问题
    // 顺序就上使用二分解决
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int len = nums.length;
        double logK = Math.log(k);
        double[] prefix = new double[len + 1];
        prefix[0] = Math.log(nums[0]);
        for (int i = 0; i < len; i++) {
            prefix[i + 1] = prefix[i] + Math.log(nums[i]);
        }
        int total = 0;
        for (int i = 1; i <= len; i++) {
            int begin = i;
            int end = len;
            int result = len;
            while (begin <= end) {
                int mid = begin + ((end - begin) >> 1);
                if (prefix[mid] < prefix[i] + logK - 1e-9) {
                    begin = mid + 1;
                    result = mid;
                } else {
                    end = mid - 1;
                }
            }
            total += result - i + 1;
        }
        return total;
    }

    // 对于right - left + 1
    public int numSubarrayProductLessThanK1(int[] nums, int k) {
        if (k <= 1) return 0;
        int len = nums.length;
        int left = 0;
        int total = 1;
        int result = 0;
        for (int right = 0; right < len; right++) {
            total *= nums[right];
            if (total >= k) total /= nums[left++];
            result += right - left + 1;
        }
        return result;
    }

}
